/*
 * =====================================================================================
 *
 *       Filename:  limingle.c
 *
 *    Description:  caculate average values of each level's nodes of a binary tree.
 *
 *        Created:  2020-08-23 19:02
 *
 *         Author:  limingle
 *          Email:  lml@xdja.com
 *   Organization:  XDJA Tech.CO.ltd.
 *
 * =====================================================================================
 */

#include <stdio.h>
#include <stdlib.h>

typedef struct binary_tree {
    int value;
    struct binary_tree *left;
    struct binary_tree *right;
} bin_tree;

typedef struct avg_info {
    unsigned count;
    float avg;
    struct avg_info *next;
}avg_info, *avg_list;

void _avg_by_level(bin_tree *bt, avg_list *l_avg)
{
    if (bt != NULL)
    {
        if (*l_avg == NULL)
        {
            *l_avg = calloc(1, sizeof(avg_info));
        }

        {
            float sum = (*l_avg)->count * (*l_avg)->avg;
            (*l_avg)->count++;

            (*l_avg)->avg = (sum + bt->value) / (*l_avg)->count;
        }

        _avg_by_level(bt->left, &((*l_avg)->next));
        _avg_by_level(bt->right, &((*l_avg)->next));
    }
}

avg_info *avg_by_level(bin_tree *bt)
{
    avg_info *avg = NULL;
    _avg_by_level(bt, &avg);
    return avg;
}

bin_tree *new_bin_tree(int *val)
{
    bin_tree *ret = NULL;
    if (val != NULL)
    {
        ret = calloc(1, sizeof(bin_tree));
        ret->value = *val;
    }
    return ret;
}

int *str_to_int(char *str, int *int_val)
{
    int *ret = int_val;

    do {
        char *endptr = NULL;
        long val = strtol(str, &endptr, 10);
        if (val == 0 && *str != '\0' && *endptr != '\0')
        {
            ret = NULL;
            break;
        }

        if (int_val == NULL)
        {
            ret = malloc(sizeof(int));
        }

        *ret = val;
    } while (0);

    return ret;
}

bin_tree **bt_arrays_from_strs(char *strs[], size_t len)
{
    if (strs == NULL || len == 0)
    {
        return NULL;
    }
    bin_tree **ret = calloc(len, sizeof(bin_tree *));
    int value;
    size_t i;
    for (i = 0; i < len; i++)
    {
        ret[i] = new_bin_tree(str_to_int(strs[i], &value));
    }

    return ret;
}

void free_bt_arrays(bin_tree **bts_array, size_t len)
{
    if (bts_array != NULL)
    {
        size_t i;
        for (i = 0; i < len; i++) {
            if (bts_array[i]!=NULL)
            {
                free(bts_array[i]);
            }
        }

        free(bts_array);
    }
}

bin_tree *generate_from_array(bin_tree *array[], size_t len)
{
    if (len > 1)
    {
        bin_tree **from = array;
        bin_tree **next = from + 1;
        bin_tree **end = array + len;

        while (from != next && next != end)
        {
            do {
                if (*from == NULL)
                {
                    break;
                }
                (*from)->left = *next;
                next++;

                if (next == end)
                {
                    break;
                }

                (*from)->right = *next;
                next++;

            } while (0);

            from++;
        }
    }

    return *array;
}

int main(int argc, const char *argv[])
{
    char *a[] = {"1", "2", "3", "4", "5", "null", "6"};
    size_t len = sizeof(a)/sizeof(a[0]);

    bin_tree **bts_array = bt_arrays_from_strs(a, len);
    bin_tree *bt = generate_from_array(bts_array, len);
    {
        avg_info *info = avg_by_level(bt);
        while (info != NULL)
        {
            avg_info *next = info->next;
            printf("%.2f\n", info->avg);
            free(info);
            info = next;
        }
    }

    free_bt_arrays(bts_array, len);
    return 0;
}
